﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinarTtree.LowestCommonAncestor
{
    class MainProject
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            TreeNode treeNode = new TreeNode(3,new TreeNode(5,new TreeNode(6),new TreeNode(2,new TreeNode(7),new TreeNode(4))),new TreeNode(1,new TreeNode(0),new TreeNode(8)));
            //TreeNode treeNode = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
            Console.WriteLine(LowestCommonAncestor(treeNode, new TreeNode(5), new TreeNode(7))?.val);
            Console.ReadKey();
        }

        /// <summary>
        /// 递归
        /// </summary>
        /// <param name="root"></param>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        public static TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
        {
            //Dictionary<int, List<int>> dic = new Dictionary<int, List<int>>();

            TreeNode res = null;
            GetHava(root, p.val, q.val,ref res);
            return res;
        }
        public static bool GetHava(TreeNode treeNode, int p, int q,ref TreeNode res)
        {
            if (treeNode==null) return false;
         
            bool left = GetHava(treeNode.left, p, q,ref res);
            bool right = GetHava(treeNode.right, p, q,ref res);

            if((left||right) && (treeNode.val == q || treeNode.val == p)) res = treeNode;

            if (treeNode.val == q || treeNode.val == p) return true;

            if (left && right) res = treeNode;

            return left || right;
        }
    }
}
